#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "hash.h" 

unsigned jenkins_one_at_a_time_hash(char *key)
{
    unsigned hash = 0;

    for (; *key; ++key) 
	{
        hash += *key;
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}


List *slist_prepend(List *list, Pointer data, char* key)
{
	List* newlist;
    newlist=(List*)malloc(sizeof(List));
	newlist->key=key;
    newlist->data=data;
    newlist->next=list;
    return newlist;
}

void slist_foreach(List *list, void (*f)(char *key, Pointer data))
{
	while(list!=NULL)
	{
		f(list->key, list->data);
		list=list->next;
	}
}

void ht_init(HashTable *ht, size_t size, HashFunction hf, Destructor dtor)
{
	size_t i;
	ht = (HashTable*)malloc(sizeof(HashTable));
	ht->table=(List**)malloc(sizeof(List)*size);
	ht->size=size;
	if(hf!=NULL)
	{
		ht->hf=hf;
	}
	else
	{
		hf=jenkins_one_at_a_time_hash;
	}
	if(dtor!=NULL)
	{
		ht->dtor=dtor;
	}
	else
	{
		ht->dtor=NULL;
	}
	for(i=0; i<ht->size; i++)
	{
		ht->table[i]=NULL;
	}
}

void ht_destroy(HashTable *ht)
{
	size_t i;
	if(ht->dtor==NULL)
	{
		for(i=0; i<ht->size; i++)
		{
			free(ht->table[i]);
		}
	}
	else
	{
		for(i; i<ht->size; i++)
		{
			ht->dtor(ht->table[i]->data);
			free(ht->table);
		}
	}
	free(ht->table);
	free(ht);
}

void ht_set(HashTable *ht, char *key, Pointer data)
{
	unsigned index;
	List * buf;
	index = ht->hf(key)%ht->size;
	buf = ht->table[index];
	if(ht->dtor==NULL)
	{
		while(buf!=NULL)
		{
			if(strcmp(buf->key, key)==0)
			{
				buf->data=data;
				return;
			}
			buf=buf->next;
		}
	}
	else
	{
		while(buf!=NULL)
		{
			if(strcmp(buf->key, key)==0)
			{
				ht->dtor(buf->data);
				buf->data=data;
				return;
			}
			buf=buf->next;
		}
	}
	ht->table[index] = slist_prepend(ht->table[index], data, key);
}

Pointer ht_get(HashTable *ht, char *key)
{
	size_t index;
	List * buf;
	index = ht->hf(key)%ht->size;
	buf = ht->table[index];
	while(buf!=NULL)
	{
		if(strcmp(buf->key, key)==0)
		{
			return buf->data;
		}
		buf=buf->next;
	}
	return NULL;
}

int ht_has(HashTable *ht, char *key)
{
	size_t index;
	List * buf;
	index = ht->hf(key)%ht->size;
	buf = ht->table[index];
	while(buf!=NULL)
	{
		if(strcmp(buf->key, key)==0)
		{
			return 1;
		}
		buf=buf->next;
	}
	return 0;
}

void ht_delete(HashTable *ht, char *key)
{
	size_t index;
	List * buf;
	List * buf2;
	index = ht->hf(key)%ht->size;
	buf = ht->table[index];
	if(buf==NULL) 
	{
		return;
	}
	while(buf->next!=NULL)
	{
		buf2=buf;
		if(strcmp(buf->key, key)==0)
		{
			if(ht->dtor!=NULL)
			{
				ht->dtor(buf->data);
				buf2->next=buf->next;
				free(buf);
				return;
			}
			else
			{
				buf2->next=buf->next;
				free(buf);
				return;
			}
		}
		buf=buf->next;
	}
	buf2=buf;
	if(strcmp(buf->key, key)==0)
	{
		if(ht->dtor!=NULL)
		{
			ht->dtor(buf->data);
			buf2->next=buf->next;
			free(buf);
			return;
		}
		else
		{
			buf2->next=buf->next;
			free(buf);
			return;
		}
	}
}

void ht_traverse(HashTable *ht, void (*f)(char *key, Pointer data))
{
	size_t i;
	List * buf;
	for(i=0; i<ht->size; i++)
	{
		buf=ht->table[i];
		slist_foreach(buf, f);
	}
}

void ht_resize(HashTable *ht, size_t new_size)
{
	List ** new_table;
	List * buf;
	size_t i;
	size_t index;
	new_table=(List**)malloc(sizeof(List)*new_size);
	for(i=0; i<ht->size; i++)
	{
		buf=ht->table[i];
		while(buf!=0)
		{
			index = ht->hf(buf->key) % new_size;
			slist_prepend(new_table[index], buf->data, buf->key);
			buf=buf->next;
		}
		free(ht->table[i]);
	}
	free(ht->table);
	ht->table=new_table;
	ht->size=new_size;
}


